#
# @lc app=leetcode.cn id=17 lang=python3
#
# [17] 电话号码的字母组合
#
# https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/description/
#
# algorithms
# Medium (54.02%)
# Likes:    806
# Dislikes: 0
# Total Accepted:    136.7K
# Total Submissions: 252.8K
# Testcase Example:  '"23"'
#
# 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
#
# 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
#
#
#
# 示例:
#
# 输入："23"
# 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
#
#
# 说明:
# 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
#
#

# @lc code=start

class Solution:
    '''
    42 ms
    '''

    def letterCombinations(self, digits: str) -> List[str]:
        self.mapping = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }

        return self.oneLetter([], digits)

    def oneLetter(self, results: List[str], digits: str) -> List[str]:
        if not digits and len(digits) == 0:
            return results

        newResults = []

        digit = digits[0]
        todo = self.mapping[digit]

        if not results or len(results) == 0:
            for letter in todo:
                newResults.append(letter)
        else:
            for r in results:
                for t in todo:
                    newResults.append(r + t)

        if len(digits) > 1:
            return self.oneLetter(newResults, digits[1:])

        return newResults

# @lc code=end
